package Offer;

/**
 * @Author: wangliuyang
 * @Date: 2021/6/14 09:38
 * @Description: 面试题 17.24. 最大子矩阵
 */
public class MaxMatrix {
    public int[] getMaxMatrix(int[][] matrix) {
        if (matrix == null || matrix.length ==0) {
            return null;
        }
        int m = matrix.length;
        int max = Integer.MIN_VALUE;
        int s[] = null;
        int ans[] = new int[4];
        int start = 0,end = 0;
        int n = matrix[0].length;
        for (int i = 0; i < m; i++) {
            s = new int[n];
            for (int j = i; j < m; j++) {
                int cur = 0;        //每次遍历结束时，将矩阵的得水平坐标置为原始值，以及动态规划初始值，即假想得前一个元素值
                start = end = 0;
                for (int k = 0; k < n; k++) {
                    s[k] += matrix[j][k];
                    if (cur < 0) {
                       cur = s[k];
                        start = k;
                    }else {
                        cur =  cur + s[k];
                    }
                    if (max <= cur){
                        max = cur;
                        end = k;
                        ans[0] = i;
                        ans[1] = start;
                        ans[2] = j;
                        ans[3] = end;
                    }
                }
            }
        }
        return ans;
    }
}
